package 程序员面试金典;

import java.util.HashSet;

/**
 * 面试题 02.08. 环路检测
 * 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：tail connects to node index 1
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 * 示例 2：
 *
 *
 *
 * 输入：head = [1,2], pos = 0
 * 输出：tail connects to node index 0
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 * 示例 3：
 *
 *
 *
 * 输入：head = [1], pos = -1
 * 输出：no cycle
 * 解释：链表中没有环。
 *
 *
 * 进阶：
 *
 * 你是否可以不用额外空间解决此题？
 *
 *
 * 通过次数33,663提交次数62,407
 */
public class T02_08 {
    //使用hashSet判重
    public ListNode detectCycle(ListNode head) {

        HashSet<ListNode> hashSet = new HashSet<>();

        while (head!=null){
            if (hashSet.contains(head)){
                return head;
            }else {

                hashSet.add(head);
                head = head.next;

            }


        }

        return null;


    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}